package org.byteDance.lru;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author yu
 * @Date 2022/3/4
 */
public class LRUCache {

    public static void main(String[] args) {

        LRUCache lruCache = new LRUCache(2);

        lruCache.put(1, 2);
        lruCache.put(3, 4);
        System.out.println("获取节点：" + lruCache.get(1));

    }

    // 记录 k, v
    Map<Integer, Node> map;

    // 缓存
    LinkedNode linkedNode;

    // 最大缓存容量
    int cap;

    public LRUCache(int cap) {
        this.cap = cap;
        map = new HashMap<>();
        linkedNode = new LinkedNode();
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);

        // 重新将节点调整至链表头
        put(key, node.value);

        return node.value;
    }

    public void put(int key, int value) {

        Node node = new Node(value);

        if (map.containsKey(key)) {
            // 如果 map 包含 key
            // 删除原有 key
            linkedNode.remove(map.get(key));
            // 将节点添加至头节点
            linkedNode.addFirst(node);
            // map 覆盖原有 key
            map.put(key, node);
        }
        if (!map.containsKey(key)) {
            // 如果 map 不包含 key
            // 判断缓存长度是否等与最大
            if (linkedNode.getSize() == cap) {
                // 缓存长度等于最大，删除最不常用的那个节点，也就是最后的那个节点
                linkedNode.removeLast();
                // 同时 map 记录也清除
                map.remove(key);
            }
            // 将新节点添加至链表头
            linkedNode.addFirst(node);
            // map 记录
            map.put(key, node);
        }

    }

}

class LinkedNode {

    private Node head, tail;
    private int size;

    public void addFirst(Node node) {
        if (head == null && tail == null) {
            head = tail = node;
        } else {
            Node n = head;
            node.next = n;
            n.prev = node;
            head = node;
        }
        size++;
    }

    public void remove(Node node) {

        if (head == node && tail == node) {
            head = tail = node;
        } else if (head == node) {
            node.next.prev = null;
            head = node.next;
        } else if (tail == node) {
            node.prev.next = null;
            tail = node.prev;
        } else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        size--;

    }

    public Node removeLast() {
        Node node = tail;
        remove(node);
        size--;
        return node;
    }

    public int getSize() {
        return size;
    }

}

class Node {

    Node next, prev;
    int value;

    public Node(int value) {
        this.value = value;
    }
}